package com.zhanghp.class038;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * O(n! * n) = O(n!) <br/>
 * 有重复项数组的去重全排列<br/>
 * 测试链接 : https://leetcode.cn/problems/permutations-ii/<br/>
 *
 * @author zhanghp
 * @since 2024/6/20 14:27
 */
public class Code04_PermutationWithoutRepeatition {
    public List<List<Integer>> permuteUnique(int[] nums) {

        List<List<Integer>> ans = new ArrayList<>();

        f(nums, 0, ans);
        return ans;
    }

    /**
     * 当前cur，到之后交换并记录<br/>
     * cur + 1, 从cur+1。。。nums.length 交换并记录<br/>
     * 。。。
     *
     * @param nums
     * @param cur
     * @param ans
     */
    public void f(int[] nums, int cur, List<List<Integer>> ans) {
        if (cur == nums.length) {
            List<Integer> l = new ArrayList<>();
            for (int it : nums) {
                l.add(it);
            }
            ans.add(l);
        } else {
            // 如果换过一次此数字，则下回不回再换相同的这个数字，规避重复
            Set<Integer> onceSet = new HashSet<>();
            for (int changeIndex = cur; changeIndex < nums.length; changeIndex++) {
                if (!onceSet.contains(nums[changeIndex])) {
                    // 添加目标交换的索引，若换cur索引，则走一遍下来，和cur索引不相同的重复数字，会交换多次，又重复
                    onceSet.add(nums[changeIndex]);
                    swap(nums, cur, changeIndex);
                    f(nums, cur + 1, ans);
                    swap(nums, cur, changeIndex);
                }

            }
        }
    }

    public void swap(int[] num, int a, int b) {
        if (a == b) {
            return;
        }
        num[a] ^= num[b];
        num[b] ^= num[a];
        num[a] ^= num[b];
    }
}
